package SortAlgorithm;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 10:23 2021/3/5
 * @Description：快速排序
 */

import org.junit.Test;

import java.util.Random;

/**
 * 1.如何选取轴值？
 * 2.如何实现分割（一次划分）？
 * 3.如何处理分割得到的两个待排序子序列？
 * 4.如何判别快速排序的结束？
 */
public class QuickSort {


    void quickSort(int[] data, int start, int end) {
        if (start < end) { //递归结束条件，即序列中只有一个元素，显然已经排好序
            int postion = partition(data, start, end);

            quickSort(data, start, postion - 1);
            quickSort(data, postion + 1, end);

        }
    }

    int Partition(int[] data, int start, int end) {

        // 轴值选取第一个值。这里是将轴值放在第一个位置
        int pivot = data[start];

        int i = start, j = end;

        while (i < j) {
            // 从后向前扫描，比较和轴值的大小，若比轴值大，则继续扫描，否则将较小的值和轴值交换
            while (i < j && data[i] <= data[j]) {
                j--;
            }
            // 当前面的while条件不满足时表示右边的值比左边的小，则执行交换
            if (i < j) {
                swap(data, i, j);
            }

            // 从前向后扫描，比较与轴值的小，若比轴值小，则不动，继续扫描
            while (i < j && data[i] <= data[j]) {
                i++;
            }
            if (i < j) {
                swap(data, i, j);
            }
        }

        return i;
    }

    int partition(int[] data, int start, int end) {
        // 随机选取轴值
        Random random = new Random();
        int index = start + (int) (random.nextDouble() * (end - start + 1));
        int value = data[index];//轴值

        // 将选取的这个索引值放到子序列的第一个位置
        swap(data, start, index);

        // 设置两个指针，指向最左和最右
        int i = start, j = end;

        while (i < j) {
            // 从后向前扫描，比较和轴值的大小，若比轴值大，则继续扫描，否则将较小的值和轴值交换
            while (i < j && value <= data[j]) {
                j--;
            }
            if (i < j) {
                // 当前面的while条件不满足时表示右边的值比左边的小，则执行交换
                swap(data, i, j);
            }
            // 从前向后扫描，比较与轴值的小，若比轴值小，则不动，继续扫描
            while (i < j && value >= data[i]) {
                i++;
            }
            if (i < j) {
                swap(data, i, j);
            }
        }

        return i;
    }

    /**
     * 为什么是地址传递？
     *
     * @param data
     * @param i
     * @param j
     */
    void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    @Test
    public void test() {
        int[] testArray = {100, 8, 4, 6, 7, 2, 1, 10};

        quickSort(testArray, 0, 7);

        for (int i : testArray) {
            System.out.print(i + ",");
        }

    }
}
